

In [ ]:

    
%%HTML
<style>
.container { width:100% }
</style>

Brute Force CSP Solver

Utility Functions

The function arb(S) takes a set S as input and returns an arbitrary element from this set. The set Sis not changed.



In [ ]:

    
def arb(S):
    for x in S:
        return x

The procedure solve(P) takes a a constraint satisfaction problem P as input. Here P is a triple of the form $$ \mathcal{P} = \langle \mathtt{Vars}, \mathtt{Values}, \mathtt{Constraints} \rangle $$ where

$\mathtt{Vars}$ is a set of strings which serve as variables,
$\mathtt{Values}$ is a set of values that can be assigned to the variables in $\mathtt{Vars}$.
$\mathtt{Constraints}$ is a set of formulas from first order logic.
Each of these formulas is called a constraint of $\mathcal{P}$.



In [ ]:

    
def solve(P):
    return brute_force_search({}, P)

The function brute_force_search takes two arguments:

Assignment is a partial variable assignment that is represented as a dictionary. Initially, this assignment will be the empty dictionary. Every recursive call of brute_force_search adds the assignment of one variable to the given assignment.
csp is a constraint satisfaction problem.

The implementation of brute_force_search works as follows:

If all variables have been assigned a value, the dictionary Assignment will have the same number of entries as the set Variables has elements. Hence, in that case Assignment is a complete assignment of all variables and we have to test whether all constraints are satisfied. This is done using the auxiliary procedure check_all_constraints.
Otherwise, we pick a variable that has not been assigned and try all possible values for this variable.



In [ ]:

    
def brute_force_search(Assignment, csp):
    Variables, Values, Constraints = csp
    if len(Assignment) == len(Variables): # all variables have been assigned
        if check_all_constraints(Assignment, Constraints):
            return Assignment
        else:
            return None
    var = arb(Variables - Assignment.keys())
    for value in Values:
        NewAss = Assignment.copy()
        NewAss[var] = value
        result = brute_force_search(NewAss, csp)
        if result != None:
            return result

The function check_all_constraints takes two arguments:

Assignment is a variable assignment that is represented as a dictionary.
Constraints is a set of Boolean Python expressions. The function returns True iff all these expression evaluate as True using the given Assignment.

Below, we have to create a copy of Assignment since the function eval modifies the assignment given to it.



In [ ]:

    
def check_all_constraints(Assignment, Constraints):
    A = Assignment.copy()
    return all(eval(f, A) for f in Constraints)

The notebook N-Queens-Problem-CSP.ipynb provides the function create_csp(n) that returns a CSP encoding the n queens puzzle.



In [ ]:

    
%run N-Queens-Problem-CSP.ipynb



In [ ]:

    
P = create_csp(8)

Brute force search takes about 31 seconds on my desktop to solve the eight queens puzzle.



In [ ]:

    
%%time
Solution = solve(P)
print(f'Solution = {Solution}')



In [ ]:

    
show_solution(Solution)



In [ ]: